
//
// Created by Administrator on 2021/10/20.
//给你两个大小为 n x n 的二进制矩阵 mat 和 target 。现 以 90 度顺时针轮转 矩阵 mat 中的元素 若干次 ，如果能够使 mat 与 target 一致，返回 true ；否则，返回 false 。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/determine-whether-matrix-can-be-obtained-by-rotation
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    /**
     * 判断一个矩阵旋转后能不能变成另一个矩阵
     * @param mat
     * @param target
     * @return
     */
    bool findRotation(vector<vector<int>> &mat, vector<vector<int>> &target) {
        for (int i = 0; i < 4; ++i) {
            rotate2(mat);
            if (mat == target)
                return true;
        }
        return false;
    }

    void rotate(vector<vector<int>> &mat) {
        int n = mat.size();
        vector<vector<int>> newMat(n, vector<int>(n, 0));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                newMat[j][n - 1 - i] = mat[i][j];
            }
        }
        mat = newMat;
    }
    void rotate2(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }

};

int main() {
    vector<vector<int>> mat{{0, 0, 0},
                            {0, 1, 0},
                            {1, 1, 1}};
    vector<vector<int>> target{{1, 1, 1},
                               {0, 1, 0},
                               {0, 0, 0}};
    Solution solution;
    cout << (solution.findRotation(mat, target) ? "true" : "false") << endl;

    return 0;
}
